package recursive.fib;
/**
 * @Date 2020/03/29
 * @author 王光浩
 * @Thinking 使用记忆化法（备忘录法）
 * @Aanalysis 时间复杂度O（n），空间复杂度O（n），从指数的时间复杂度到n的时间复杂度。
 */
public class MyMethodTwo {
	public int fib(int N) {
		int[] note=new int[N+1]; //因为是从 0~N
		return helper(N,note);
	}
	private int helper(int N,int[] note) {
		if(N<2)return N;
		if(note[N]==0)
			note[N]=helper(N-1,note)+helper(N-2,note);
		return note[N];
	}
}
